"""
使用二分法查找半有序数组的无序点 -> [153]寻找旋转排序数组中的最小值
分析： 半有序数组的无序点的特点： 数组中的最小值
思路： 因为是升序排列，两段数组之间的左值始终小于右值，故使用二分法查找时，mid值与right相比较，分类讨论：
      1）nums[left]<nums[mid]<nums[right]: 最小值在左边,收缩右边界，right = mid
      2）nums[left]>nums[mid]但nums[mid]<nums[right]: 最小值还是在左边，收缩右边界
      3)nums[left]>nums[mid]>nums[right]：递增数列，这种情况不可能出现，排除！
      4)nums[left]<nums[mid]>nums[right]: 最小值在右边，需要收缩左边界
      综上所述，只要nums[mid] < nums[right],都需要收缩右边界：right = mid (为什么不-1？可能会跳过最小值)
              只要nums[mid] > nums[right],都需要收缩左边界: left = mid + 1
     退出循环后(left==right)，输出left或者right对应的数即可
"""

from typing import List


def solution(nums: List[int]):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[right]


if __name__ == '__main__':
    num1 = [7]
    num2 = [4, 5, 6, 7, 1, 2, 3]
    num3 = [7, 8, 4, 5, 6]
    print(solution(num1))
